题目：找出一个字符串中的最长回文子串！

回文字符串的子串也是回文，比如P[i,j]（表示以i开始以j结束的子串）是回文字符串，那么P[i + 1, j - 1]也是回文字符串，这样最长回文子串就能分解成一系列子问题了。

首先定义状态方程和转移方程，P[i,j] = 0表示子串[i,j]不是回文子串，P[i,j] = 1表示子串[i, j]是回文子串：

1
2
3
P[i, i] = 1;
P[i, j] = P[i + 1, j - 1], if s[i] == s[j];
P[i, j] = 0, if s[i] != s[j];

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
string findLongestPalindrome(string& s) {
  const int length = s.size();
  int maxLength = 0;
  int start;
  bool P[50][50] = {false};
  for (int i = 0; i < length; i++) { // 初始化
    P[i][i] = true;
    if (i < length - 1 && s.at(i) == s.at(i + 1)) {
      P[i][i + 1] = true;
      start = i;
      maxLength = 2;
    }
  }
  
  for (int len = 3; len <= length; len++) { // 子串长度
    for (int i = 0; i <= length - len; i++) { // 子串起始地址
      int j = i + len - 1; // 子串结束地址
      if (P[i + 1][j - 1] && s.at(i) == s.at(j)) {
        p[i][j] = true;
        maxLength = len;
        start = i;
      }
    } 
  }
  
  if (maxLength > 2) {
    return s.substr(start, maxLength);
  }
  return nullptr;
}